import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;

public class Test {
    public int triangleNumber(int[] nums) {//有效三角形的个数
        int n=nums.length;
        int sum=0;
        Arrays.sort(nums);
        for(int i=n-1;i>=2;i--){
            int left=0,right=i-1;
            while(left<right){
                if(nums[left]+nums[right]>nums[i]){
                    sum+=right-left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        return sum;
    }

    public int[] twoSum(int[] nums, int target) {
        int left=0,right=nums.length-1;
        while(left<right){
            int sum=nums[left]+nums[right];
            if(sum>target){
                right--;
            }else if(sum<target){
                left++;
            }else {
                return new int[]{nums[left],nums[right]};
            }
        }
        return new int[]{};
    }

    public static void main(String[] args) {

        //有效三角形个数测试
        int[] nums={4,2,3,4};
        int ret=new Test().triangleNumber(nums);
        System.out.println("有效三角形个数为:"+ret);

        //和为s的数
        int[] nums1 = {1,2,3,4,6,7,8,11};
        Test test=new Test();
        int[] nums2 = test.twoSum(nums1, 6);
        System.out.println("和为s的两个数为:"+Arrays.toString(nums2));
    }
}
